Free Solved Question Paper of BCS42 - Introduction to Algorithm Design for December 2022

1. (a) Define $\Theta$ (big theta) notation. By using a basic definition, show that $7n^2 + 8n - 9 = \Theta(n^2)$. (4 marks)

Answer :

The big theta notation, $\Theta$, is used to describe an asymptotically tight bound on the growth rate of a function. For a given function $f(n)$, we say $f(n) = \Theta(g(n))$ if there exist positive constants $c_1$, $c_2$, and $n_0$ such that for all $n \ge n_0$,
$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$.

To show that $7n^2 + 8n - 9 = \Theta(n^2)$, we need to find constants $c_1$, $c_2$, and $n_0$ such that:
$c_1 \cdot n^2 \le 7n^2 + 8n - 9 \le c_2 \cdot n^2$ for all $n \ge n_0$.

First, for the upper bound, we can observe that:
$7n^2 + 8n - 9 \le 7n^2 + 8n$ since $-9$ is negative.
$7n^2 + 8n \le 7n^2 + 8n^2 = 15n^2$ for all $n \ge 1$.
So, we can choose $c_2 = 15$ and $n_0 = 1$.

Next, for the lower bound, we have:
$7n^2 + 8n - 9 \ge 7n^2$ for all $n \ge 1$ since $8n - 9$ can be zero or positive for $n \ge 1$.
So, we can choose $c_1 = 7$ and $n_0 = 1$.

Therefore, by definition, $7n^2 + 8n - 9 = \Theta(n^2)$.

1. (b) Apply Bubble sort algorithm to sort the following list of numbers. Show the procedure step-by-step. Calculate the number of exchange and comparison operations required in the algorithm :
15, 8, 7, 11, 25, 13, 12, 4 (4 marks)

Answer :

The Bubble sort algorithm sorts a list by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The process is repeated until the list is sorted.

Initial list: 15, 8, 7, 11, 25, 13, 12, 4

Pass 1:
Compare 15 and 8, swap: 8, 15, 7, 11, 25, 13, 12, 4
Compare 15 and 7, swap: 8, 7, 15, 11, 25, 13, 12, 4
Compare 15 and 11, swap: 8, 7, 11, 15, 25, 13, 12, 4
Compare 15 and 25, no swap: 8, 7, 11, 15, 25, 13, 12, 4
Compare 25 and 13, swap: 8, 7, 11, 15, 13, 25, 12, 4
Compare 25 and 12, swap: 8, 7, 11, 15, 13, 12, 25, 4
Compare 25 and 4, swap: 8, 7, 11, 15, 13, 12, 4, 25

Pass 2:
Compare 8 and 7, swap: 7, 8, 11, 15, 13, 12, 4, 25
Compare 8 and 11, no swap: 7, 8, 11, 15, 13, 12, 4, 25
Compare 11 and 15, no swap: 7, 8, 11, 15, 13, 12, 4, 25
Compare 15 and 13, swap: 7, 8, 11, 13, 15, 12, 4, 25
Compare 15 and 12, swap: 7, 8, 11, 13, 12, 15, 4, 25
Compare 15 and 4, swap: 7, 8, 11, 13, 12, 4, 15, 25

Pass 3:
Compare 7 and 8, no swap: 7, 8, 11, 13, 12, 4, 15, 25
Compare 8 and 11, no swap: 7, 8, 11, 13, 12, 4, 15, 25
Compare 11 and 13, no swap: 7, 8, 11, 13, 12, 4, 15, 25
Compare 13 and 12, swap: 7, 8, 11, 12, 13, 4, 15, 25
Compare 13 and 4, swap: 7, 8, 11, 12, 4, 13, 15, 25

Pass 4:
Compare 7 and 8, no swap: 7, 8, 11, 12, 4, 13, 15, 25
Compare 8 and 11, no swap: 7, 8, 11, 12, 4, 13, 15, 25
Compare 11 and 12, no swap: 7, 8, 11, 12, 4, 13, 15, 25
Compare 12 and 4, swap: 7, 8, 11, 4, 12, 13, 15, 25

Pass 5:
Compare 7 and 8, no swap: 7, 8, 11, 4, 12, 13, 15, 25
Compare 8 and 11, no swap: 7, 8, 11, 4, 12, 13, 15, 25
Compare 11 and 4, swap: 7, 8, 4, 11, 12, 13, 15, 25

Pass 6:
Compare 7 and 8, no swap: 7, 8, 4, 11, 12, 13, 15, 25
Compare 8 and 4, swap: 7, 4, 8, 11, 12, 13, 15, 25

Pass 7:
Compare 7 and 4, swap: 4, 7, 8, 11, 12, 13, 15, 25

Sorted list: 4, 7, 8, 11, 12, 13, 15, 25

Total number of comparisons: 28
Total number of exchanges: 13

1. (c) Solve the following recurrence problem using recursion tree method : $T(n) = 4T\left(\frac{n}{2}\right) + n$ (6 marks)

Answer :

1. (d) Draw any three spanning trees of the following weighted connected graph : (6 marks)

Answer :

Here are three possible spanning trees of the given graph:

Spanning Tree 1:

- Edge a-b (weight 10) - Edge b-e (weight 7) - Edge b-d (weight 6) - Edge a-c (weight 12)

Spanning Tree 2:

- Edge a-c (weight 12) - Edge c-d (weight 8) - Edge d-e (weight 9) - Edge a-b (weight 10)

Spanning Tree 3:

- Edge b-e (weight 7) - Edge b-d (weight 6) - Edge c-d (weight 8) - Edge a-c (weight 12)

Note: These spanning trees are described textually as I cannot draw images. Each spanning tree includes all 5 vertices (a, b, c, d, e) and 4 edges, forming a tree structure without cycles.

Each of these spanning trees connects all vertices of the original graph without forming any cycles, which is the definition of a spanning tree. The weights of the edges are included for reference, but they don't affect whether a subgraph is a spanning tree or not - that's determined solely by the structure.

2. (a) Give an example for each complexity class :
$O(n)$ , $O(n^2)$ , $O(n \log n)$ (3 marks)

Answer :

Examples for each complexity class are as follows:

1. $O(n)$: An example of an algorithm with $O(n)$ complexity is a simple linear search. In a linear search, we go through each element in the array exactly once until we find the target element or reach the end of the array.

2. $O(n^2)$: An example of an algorithm with $O(n^2)$ complexity is bubble sort. In bubble sort, we repeatedly compare and swap adjacent elements if they are in the wrong order. This process is repeated for each element in the array, leading to a quadratic time complexity.

3. $O(n \log n)$: An example of an algorithm with $O(n \log n)$ complexity is merge sort. In merge sort, we divide the array into two halves, sort each half recursively, and then merge the sorted halves. The divide and merge operations each take $O(\log n)$ time, and there are $n$ elements to process, leading to $O(n \log n)$ complexity.

2. (b) (i) Write the Euclid algorithm to compute GCD of two non-negative integers and apply it to find $GCD(325, 95)$. Show all the intermediate steps. (4 marks)

Answer :

The Euclidean algorithm to compute the GCD of two non-negative integers a and b is as follows:

1. If b = 0, return a as the GCD.
2. Otherwise, divide a by b and let r be the remainder.
3. Set a = b and b = r.
4. Go back to step 1.

Applying this algorithm to find $GCD(325, 95)$:

Step 1: $325 = 3 \times 95 + 40$
a = 325, b = 95, r = 40

Step 2: $95 = 2 \times 40 + 15$
a = 95, b = 40, r = 15

Step 3: $40 = 2 \times 15 + 10$
a = 40, b = 15, r = 10

Step 4: $15 = 1 \times 10 + 5$
a = 15, b = 10, r = 5

Step 5: $10 = 2 \times 5 + 0$
a = 10, b = 5, r = 0

Since the remainder is 0, we stop here. The GCD is the last non-zero remainder, which is 5.

Therefore, $GCD(325, 95) = 5$.

2. (b) (ii) Perform the Complexity Analysis of the Euclidean Algorithm. (3 marks)

Answer :

The Euclidean algorithm efficiently computes the Greatest Common Divisor (GCD) of two non-negative integers $a$ and $b$. Here’s a breakdown of its complexity:

Algorithm Recap:
→ Step 1: If $b = 0$, return $a$ as the GCD.
→ Step 2: Otherwise, compute $r$, the remainder when $a$ is divided by $b$.
→ Step 3: Update $a$ to $b$ and $b$ to $r$.
→ Step 4: Repeat from Step 1 until $b = 0$.

Complexity Analysis:
→ Time Complexity: The algorithm’s time complexity is determined by the number of iterations required to find the GCD. In the worst case, where $a$ and $b$ are Fibonacci-like numbers (such as $a = F_{n+1}$ and $b = F_n$), the number of iterations $k$ is $O(\log(\min(a, b)))$. This logarithmic behavior arises because each step reduces the problem size by approximately half when $b$ is significantly smaller than $a$.
→ Space Complexity: The algorithm’s space complexity is constant $O(1)$, as it only requires a fixed amount of additional memory regardless of the input size. This minimal space usage makes it highly efficient in terms of memory.

Conclusion:
The Euclidean algorithm exhibits a time complexity of $O(\log(\min(a, b)))$ and a space complexity of $O(1)$. This efficiency makes it well-suited for calculating the GCD of large integers within a reasonable time frame and with minimal memory overhead.

3. (a) Compare between Kruskal's and Prim's algorithms. (3 marks)

Answer :

Kruskal's and Prim's algorithms are both used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. Here's a comparison between the two:

1. Approach:
→ Kruskal's algorithm: Builds the MST by selecting edges in order of increasing weight, regardless of connectivity.
→ Prim's algorithm: Builds the MST by growing a single tree from a starting vertex, always adding the lowest-weight edge that connects the tree to a new vertex.

2. Time Complexity:
→ Kruskal's algorithm: $O(E \log E)$ or $O(E \log V)$, where E is the number of edges and V is the number of vertices.
→ Prim's algorithm: $O(E \log V)$ with binary heap, or $O(V^2)$ with a simple implementation.

3. Graph Density:
→ Kruskal's algorithm: Generally more efficient for sparse graphs.
→ Prim's algorithm: Often performs better on dense graphs.

4. Implementation:
→ Kruskal's algorithm: Requires a disjoint-set data structure for efficient implementation.
→ Prim's algorithm: Can be implemented using a priority queue or a simple array.

5. Edge Selection:
→ Kruskal's algorithm: Considers all edges of the graph.
→ Prim's algorithm: Only considers edges connected to the current tree.

Both algorithms are guaranteed to find the MST if it exists, but their performance can vary depending on the graph structure and implementation details.

3. (b) Apply Strassen's algorithm to multiply two matrices A(4 × 4) and B(4 × 4) using divide and conquer technique and explain. (7 marks)

Answer :

Strassen's algorithm is a divide-and-conquer method for matrix multiplication that reduces the number of recursive calls compared to the standard algorithm. For 4×4 matrices, we'll apply the algorithm step by step:

Step 1: Divide the matrices

First, we divide matrices A and B into 2×2 submatrices:

$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}$

Where each $A_{ij}$ and $B_{ij}$ is a 2×2 matrix.

Step 2: Calculate seven products

Strassen's algorithm computes these products:

→ $P_1 = (A_{11} + A_{22})(B_{11} + B_{22})$
→ $P_2 = (A_{21} + A_{22})B_{11}$
→ $P_3 = A_{11}(B_{12} - B_{22})$
→ $P_4 = A_{22}(B_{21} - B_{11})$
→ $P_5 = (A_{11} + A_{12})B_{22}$
→ $P_6 = (A_{21} - A_{11})(B_{11} + B_{12})$
→ $P_7 = (A_{12} - A_{22})(B_{21} + B_{22})$

Step 3: Calculate the result submatrices

The result matrix C is calculated as follows:

$C = \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix}$

Where:

→ $C_{11} = P_1 + P_4 - P_5 + P_7$
→ $C_{12} = P_3 + P_5$
→ $C_{21} = P_2 + P_4$
→ $C_{22} = P_1 - P_2 + P_3 + P_6$

Step 4: Recursive application

For 4×4 matrices, we need to recursively apply Steps 1-3 to compute each $P_i$. This involves multiplying 2×2 matrices, which can be done using the standard method or by applying Strassen's algorithm again for 2×2 matrices.

Explanation:

→ Strassen's algorithm reduces the number of multiplications from 8 (in the standard divide-and-conquer approach) to 7 for each recursive step.
→ For 4×4 matrices, we perform 7 multiplications of 2×2 matrices, each requiring 7 scalar multiplications.
→ The total number of scalar multiplications is thus 49, compared to 64 in the standard algorithm.
→ The trade-off is an increase in the number of additions/subtractions.
→ For larger matrices, the reduction in multiplications leads to improved asymptotic complexity: $O(n^{\log_2 7}) \approx O(n^{2.8074})$ compared to $O(n^3)$ for the standard algorithm.

While Strassen's algorithm provides theoretical improvement, for small matrices like 4×4, the overhead of the additional operations might not provide a practical speed-up. Its benefits become more apparent for larger matrices.

4. (a) Define the term Branch and Bound and write the problem which can be solved through this technique. (3 marks)

Answer :

Branch and Bound:

Branch and Bound is an algorithmic technique for solving optimization problems, particularly discrete and combinatorial optimization problems. It consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

Key components of Branch and Bound:

→ Branching: Dividing the problem into smaller subproblems

→ Bounding: Estimating the best possible solution for each subproblem

→ Pruning: Eliminating subproblems that cannot lead to a better solution than the current best

Problems that can be solved using Branch and Bound:

Several optimization problems can be solved using the Branch and Bound technique. Some notable examples include:

→ Traveling Salesman Problem (TSP)

→ 0/1 Knapsack Problem

→ Job Assignment Problem

→ Maximum Clique Problem

→ Integer Linear Programming

Among these, the Traveling Salesman Problem (TSP) is one of the most well-known applications of Branch and Bound. In TSP, the goal is to find the shortest possible route that visits each city exactly once and returns to the starting city. Branch and Bound can efficiently solve this NP-hard problem by systematically exploring the solution space while pruning branches that cannot lead to an optimal solution.

4. (b) Apply Dijkstra's algorithm to find the shortest path from V1 to all other nodes. Show all the intermediate steps and explain. (7 marks)

Answer :

Step 1: Initialization
→ Start at node V1.
→ Initialize distances:
→ Distance to V1: $0$
→ Distance to all other nodes: Infinity (except directly connected nodes).

Step 2: Iteration Process

1. Initial State:
→ Priority Queue: (V1, 0), (V2, ∞), (V3, ∞), (V4, ∞), (V5, ∞), (V6, ∞), (V7, ∞)

2. Iteration 1: Visit V1
→ Update distances to adjacent nodes:
→ V2: $6$ (Distance to V1 + Weight of V1 to V2), V4: $12$ (Distance to V1 + Weight of V1 to V4), V6: $8$ (Distance to V1 + Weight of V1 to V6)
→ Priority Queue after updates: (V2, 6), (V6, 8), (V4, 12)

3. Iteration 2: Visit V2
→ Update distances to adjacent nodes:
→ V3: $13$ (Distance to V2 + Weight of V2 to V3), V5: $13$ (Distance to V2 + Weight of V2 to V5)
→ Priority Queue after updates: (V6, 8), (V4, 12), (V3, 13), (V5, 13)

4. Iteration 3: Visit V6
→ Update distances to adjacent nodes:
→ V5: $18$ (Distance to V6 + Weight of V6 to V5), V3: $17$ (Distance to V6 + Weight of V6 to V3)
→ Priority Queue after updates: (V4, 12), (V3, 13), (V5, 13), (V7, 16)

5. Iteration 4: Visit V3
→ Update distance to V4: $20$ (Distance to V3 + Weight of V3 to V4)
→ Priority Queue after updates: (V4, 12), (V5, 13), (V7, 16)

6. Iteration 5: Visit V4
→ Update distance to V7: $20$ (Distance to V4 + Weight of V4 to V7)
→ Priority Queue after updates: (V5, 13), (V7, 16)

7. Iteration 6: Visit V5
→ Update distance to V7: $22$ (Distance to V5 + Weight of V5 to V7)
→ Priority Queue after updates: (V7, 16)

8. Iteration 7: Visit V7
→ No new updates.
→ Priority Queue: Empty

Final Result:
→ Shortest paths from V1:
→ V1: $0$
→ V2: $6$
→ V3: $13$
→ V4: $12$
→ V5: $13$
→ V6: $8$
→ V7: $16$

Explanation:

→ Dijkstra's algorithm systematically explores the shortest paths from the source node (V1) to all other nodes by continuously selecting the node with the smallest tentative distance.
→ It uses a priority queue to efficiently manage and update these distances, ensuring that each node is processed in order of increasing shortest path distance from V1.
→ During each iteration, the algorithm updates distances to adjacent nodes from the current node being processed, reflecting the shortest paths found so far.
→ This iterative process continues until all reachable nodes have been processed and the shortest path from V1 to each node is determined and recorded.

5. (a) Define the terms : path, cycle and a complete graph. (3 marks)

Answer :

1. Path:
A path in a graph is a sequence of vertices where each adjacent pair of vertices in the sequence is connected by an edge. More formally:

→ A path of length n from vertex $v$ to vertex $w$ is a sequence of vertices $\{v_0, v_1, ..., v_n\}$ where:

→ $v_0 = v$ (starting vertex)

→ $v_n = w$ (ending vertex)

→ There is an edge between $v_i$ and $v_{i+1}$ for $i = 0, 1, ..., n-1$

2. Cycle:
A cycle is a path that starts and ends at the same vertex, with no other repeated vertices. Specifically:

→ A cycle is a path $\{v_0, v_1, ..., v_n\}$ where $v_0 = v_n$ and n ≥ 3

→ All vertices $v_1, ..., v_{n-1}$ are distinct

3. Complete Graph:
A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. In other words:

→ A complete graph with n vertices, denoted as $K_n$, has $\frac{n(n-1)}{2}$ edges

→ Every vertex has a degree of n-1 (connected to all other vertices)

→ There are no self-loops or multiple edges between the same pair of vertices

These fundamental concepts in graph theory are crucial for understanding more complex graph structures and algorithms.

5. (b) Write a program to generate Fibonacci series of 10 terms and count :
(i) the number of times the loop will continue, and
(ii) the number of times the assignment operations will occur. (7 marks)

Answer :

Here's a C++ program that generates the Fibonacci series of 10 terms and counts the required operations:

#include <iostream>
using namespace std;

void fibonacciWithCounts() {
    int a = 0, b = 1;
    int loop_count = 0;
    int assignment_count = 2;  // Initial assignments of a and b

    cout << "Fibonacci series:" << endl;
    for (int i = 0; i < 10; i++) {
        cout << a << " ";
        int temp = b;
        b = a + b;
        a = temp;
        loop_count++;
        assignment_count += 3;  // Three assignments in each iteration
    }

    cout << "

Counts:" << endl;
    cout << "(i) Number of times the loop continued: " << loop_count << endl;
    cout << "(ii) Number of times assignment operations occurred: " << assignment_count << endl;
}

int main() {
    fibonacciWithCounts();
    return 0;
}

This program will output:

Fibonacci series:
0 1 1 2 3 5 8 13 21 34 

Counts:
(i) Number of times the loop continued: 10
(ii) Number of times assignment operations occurred: 32

Explanation of the counts:

(i) Number of times the loop continued:
The loop runs exactly 10 times to generate 10 terms of the Fibonacci series.

(ii) Number of times assignment operations occurred:
→ 2 initial assignments: $a = 0$ and $b = 1$
→ In each of the 10 iterations, there are 3 assignments: $temp = b$, $b = a + b$, and $a = temp$
→ Total assignments = 2 + (10 * 3) = 32

This C++ program efficiently generates the Fibonacci series while keeping track of the required counts. It provides a clear demonstration of both the series generation and the underlying operational complexity. Note that the assignment count is higher in this C++ version compared to the previous Python version due to the need for a temporary variable in the swap operation.