IGNOU MCA Previous Years Unsolved Papers All in One

Chapter 1: MCS-211, Design and Analysis of Algorithms

Master Of Computer Applications (MCA)

Term-End Examination, December, 2021

Time: 3 Hours

Maximum Marks: 100

Weightage: 70%

Note:       (i) Question No. 1 is compulsory.

(ii) Attempt any three Questions from the rest.

(a) Write a mathematical definition of O (big oh). Assume that the function f(n) = 2n2 + 3n + 1.

Show that f(n) = O(n2 ).                                                             5

(b) Define a recurrence relation of QuickSort algorithm and solve it using a recurrence tree.             10

(c) What are the key features of combinatorial problems ? Describe and formulate three combinatorial problems.                                                                               10

(d) Describe a task scheduling problem as an optimization problem. Apply the scheduling algorithm with deadlines to maximize the total profit to the following problem :                                           10

Jobs

2

3

4

5

4

3

(e) List all the different orders in which we can multiply five matrices M1, M2, M3, M4, M5.             10

(a) Explain the naïve string matching algorithm and derive its worst case complexity. What is its drawback ?

What will be the maximum valid shifts of a pattern in the text in the following example ?                   10

Text : a b c x y z d e f g h

Pattern : f g h

(b) What is the similarity between Dijkstra’s single source shortest path and Prim’s minimum cost spanning tree algorithms ? Apply Dijkstra’s algorithm to find the shortest path from v1 to all other vertices of the following graph :

10

3. (a) Apply Horner’s method for evaluating a polynomial expression p(x) = 6x6 + 5x5 + 4x4 – 3x3 + 8x – 7 at x = 3.

Calculate :                                                                   10

(i) How many times will the loop execute ?

(ii) What will be the total number of multiplication and addition operations ?

(b) Define a fractional knapsack problem as an optimization problem. Write a greedy method to find an optimal solution to the problem. Show the complexity of the algorithm.                               10

4. (a) Apply the DFS algorithm to the following graph with the starting vertex v1 . List the order in which vertices will be visited.

Show the complexity analysis if a graph is represented through

(i) Adjacency list, and

(ii) Adjacency matrix.                                                             10

(b) Explain P, NP and NP-complete class of problems with appropriate examples of each class.             10

(a) Apply Floyd Warshall’s algorithm and show the matrix D2 of the following graph : 10

(b) Explain the use of master method. Write and interpret all the three cases of the master method to solve recurrence relation problem.

MCS – 211

Chapter 2: MCS-211, Design and Analysis of Algorithms

Master Of Computer Applications (MCA)

Term-End Examination, June, 2022

Time: 3 Hours

Maximum Marks: 100

Weightage: 70%

Note:       (i) Question No. 1 is compulsory.

(ii) Attempt any three Questions from the rest.

1. (a)Calculate the time complexity of the following program fragments using Big Ohnotation:            5

(i) For(i=0;i

a[i]=0;

for(i=0;i

for(j=0,j

(ii) For(i=1;i≤n;i=i*2).

{

x =x +i;

}

(b)Explain the working principle of Floyd-Warshall's algorithm.                              5

(c)Define topological ordering of a graph. Write the algorithm to find topologicalordering of the following graph.Calculatethe complexity of the algorithm:                                          10

(d)Define the substitution method to solve arecurrence relation. Solve the following recurrence relation using substitution method:                                                            10

T(n)=2T(n12)+n

(e)Write Kruskal's algorithm to find minimum cost spanning tree of the following graph:                  10

2

5

A

B

E

3

8

3

9

5

C

3

7

F

D

Show complexity analysis of the algorithm and all the intermediate steps.

2.(a)Describe the most commonly used data structure for implementing Dijkstra single source shortest path algorithm.                                                                         5

(b)Prove that Subpaths of the shortest pathin a single source shortest path algorithmare also the shortest paths.                                                                              5

(c)Apply Bubble sort algorithm for the following list of numbers:                              10

12

7

Calculate its best case and worst case time complexities.

3.(a)Write and explain the procedure to find a solution to maximum bipartite matching problem with the help of an example.                                                                   7

(b)List one algorithm each for the following time complexities:                              3

(i) O(m logn)

(ii) O(logn)

(iii) O(n²)

(c)Find the optimal solution to the following instance of a fractional Knapsack problem. Show step-by-step running of the algorithm:                                                                  10

Number of objects =5

Capacity of a knapsack W=15

Pi=Profit of an object i

wi=Weight of an object i

(P₁,P₂,P₃,P₄,P₅) = (15,30,40,35,55)

(w₁,w₂,w₃,w₄,w₅) = (5,9,3,7,2)

4.(a)Explain the concept of rolling hash function applied in Rabin-Karp algorithm for string matching problem with the helpof an example.                                                            10

(b)Differentiate between greedy approach and dynamic approach to solve an optimization problem.      4

(c)Formulate the following problemsas optimization and decision problems:                        6

(i)Traveling salesperson problem

(i)Graph coloring problem

5.(a)Explain the concept of non-deterministicalgorithm with the help of an example. List the problems which belong to non-deterministic class of complexity.                                                8

(b)Whether the following is in correct order ?                                          2

1, log n, n nlog n, n², 2^n n!

(c)Construct an optimal Huffman tree and Huffman code for each character for the following set of frequencies:

A:20, B:25, C:10, D:8, E:7, F:12, G:10.

Show all the intermediate steps.                                                      10

MCS – 211

Chapter 3: MCS-211, Design and Analysis of Algorithms

Master Of Computer Applications (MCA)

Term-End Examination, December, 2022

Time: 3 Hours

Maximum Marks: 100

Weightage: 70%

Note:       (i) Question No. 1 is compulsory.

(ii) Attempt any three Questions from the rest.

1. (a) Write a mathematical definition of big omega (Ω). For the functions defined by f(n) = 3n3 + 2n2 + 1 and g(n) = 2n2 + 3, verify that f(n) = Ω(g(n)).                                                 6

(b) Explain the principle of optimality in dynamic programming, with the help of an example.             6

(c) Apply a master method to give the tight asymptotic bounds of the following recurrences :             8

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

(ii) T(n) = 9T (n/3) + n

(d) Run the Prim’s algorithm on the following graph. Assume that the root vertex is a .

Derive the complexity of the algorithm.                                                 10

(e) Apply Huffman’s algorithm to construct a Huffman’s tree and optimal binary prefix code for the letters and its frequencies as given in the following table :                                                 10

Letter

2. (a) Explain Cook-Levin’s theorem on CNF-Safisfiability problem, with the help of an example.       10

(b) (i) Apply Dijkstra’s single source shortest path algorithm to the following graph with a as starting vertex. Show all the intermediate steps.

(ii) What is the significant feature of Bellman-Ford’s algorithm which is not supported in Dijkstra’s algorithm ?                                                                               3

3. (a) Write and explain pseudocode for Ford-Fulkerson’s algorithm for maximum bipartite matching.       10

(b) Apply the partition procedure of Quicksort algorithm to the following array : [35, 10, 40, 5, 60, 25, 45, 15]

Show all the intermediate steps.                                                       10

4. (a) Apply DFS to the complete graph on four vertices. List the vertices in the order they would be visited.                                                                               7

(b) How many comparisons are needed for a binary search in a set of 512 elements ?                   3

(c) Apply Floyd-Warshall’s algorithm to the following graph and show D2 .                         10