IGNOU MCA-NEW MCS 211 Design and Analysis of Algorithm Solved Assignment ENGLISH

Please make sure your assignment questions match your current IGNOU session

MCS 211 (January 2026 - July 2026) - ENGLISH

Course Code

MCS-211

Course Title

Design and Analysis of Algorithms

Assignment Number :

MCA_NEW(I)/211/Assign/2026

Maximum Marks

: :

100

Weightage :

30%

Last Dates for Submission :

30 0th April 2026 (for January Session) st

31 October 2026 (for July Session)

This assignment has four questions (80 Marks). Answer all questions. The remaining 20 marks are for your viva voce examination. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the presentation format.

Q1:a) Design and develop an efficient algorithm to find all the prime numbers in the range 2 to 10000.Access the complexity of this algorithm?

b) Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times.

c) A sorted array of size n contains several duplicate values. Design an algorithm to search a value in the array. The algorithm should output all the indexes where the searched value exists. Explain the worst time complexity of this algorithm.

d) Explain the Big Theta (O) and Big Omega (2) notations with the help of a diagram. What is the need of asymptotic bounds? Also, list the shortcomings of the asymptotic bounds. Find the Big O, O and 2 bounds for the following function:

f(n)=999n3+999999n+100

e) Write the Right to Left binary exponentiation algorithm. Demonstrate the use of this algorithm to compute the value of 523. Show all steps of the computation. Explain the worst-case complexity of this algorithm.

f) Write and explain the Insertion sort algorithm. Discuss its best and worst-case time complexity.

g) What is a recurrence relations? When are they used? Solve the following recurrence relations using the Master's method

Here are the equations from the image written in LaTeX format, along with a plain text version.

$

$ 

Q2: a) How can an optimisation problem be represented mathematically. Explain with the help of an example. Explain the steps of designing a Greedy solution for an optimisation problem. Also explain the concept of local and global optimal solutions. Solve the following fractional Knapsack problem using greedy approach. Show all the steps.

Suppose there is a knapsack of capacity 10 Kg and the following 5 items are to packed in it. The weight and profit of the items are as under:

(p1, p2,..., ps) = (10, 20,18,15,5) (W1, W2,..., Ws) = (2, 5, 3, 5, 1)

b) Assuming that data to be transmitted consists of only characters'a' to 'g', design the Huffman codes 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:25, b:3, c:2,d:6, e:40, f:14, g:10

c) Expalin the PARTITION algorithm of the Quick Sort taking the last element as pivot. Demonstrate the use of Quick sort algorithm for sorting the following data of size 8: [1, 5, 8, 11, 16, 19, 29, 38]. Compute the complexity of the worst case of Quick Sort algorithm.

d) Explain the divide and conquer approach of multiplying two large matrices of size 16 x 16. Compute the time complexity of this approach.

Consider the following Graph: 

 

Figure 1: A sample weighted Grари

a) Write the Kruskal's algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Kruskal'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.

Bellman-Ford's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation.

search (where pi represents the probability that the search will be for the key node ki, whereas qi represents that the search is for dummy node di. Make suitable assumptions, if any) 

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

Matrix	Dimension
A1	25 × 10
A2	10 × 35
A3	35 × 10
A4	10 × 30

e) Explain the Knuth Morris Pratt (KMP) algorithm for finding a string in a text/paragraph with the help of an example. Find the time complexity of this algorithm.

Q4:a) Explain the term intractable problems with the help of an example. Define the following problems with the help of an example.

(i) Travelling Salesman Problem

(ii) Clique Problem

b) What are NP and NP-Complete classes of problems? Explain with the help of at least two examples each.

c) Define the relationship between P, NP, NP-Complete and NP-Hard classes of problems. How are they different from each other.

d) Describe the following Problems:

(i) 3-CNF SAT Problem

(ii) 0/1 Knapsack Problem

(iii) Vertex Cover Problem

(iv) Graph colouring problem

 

MCS 211 (January 2025 - July 2025) - ENGLISH

Course Code:MCS-211

Course Title:Design and Analysis of Algorithms

Assignment Number:MCA_NEW(I)/211/Assign/2025

Maximum Marks:100

Weightage:30%

Last Dates for Submission :30 April 2025 (for January Session)

st 31 October 2025 (for July Session)

This assignment has four questions (80 Marks). Answer all questions. The remaining 20 marks are for viva voce. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme guide for the presentation format.

Q1: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?

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

c) Write an algorithm to multiply two square matrices of order n*n. Also explain the time complexity of this algorithm.

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 notation with the help of a diagram. Find the Big O-notation and -notation for the function:

 

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

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

g) What are the uses of recurrence relations? Solve the following recurrence relations using the Master's method

,

,Q2: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 packed in it. The weight and profit of the items are as under:

Select a subset of the items that maximises the profit while keeping the total weight below or equal to the given capacity.

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

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.

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.

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

Q3: Consider the following Graph:

a) 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.

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.

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 pi represents the probability that the search will be for the key node ki, whereas qi represents that the search is for dummy node di. Make suitable assumptions, if any)

i	0	1	2	3	4
pi		0.10	0.15	0.20	0.10
qi	0.05	0.10	0.10	0.10	0.10

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

Matrix	Dimension
A1	10 × 15
A2	15 × 5
A3	5 × 20
A4	20 × 10

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

Q4: 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

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

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

d) Define the following Problems:

(i) SAT Problem

(ii) Clique problem

(iii) Hamiltonian Cycle Problem

(iv) Subset Sum Problem

Q: How will I receive the PDF?
A: Immediately after payment, the download link will appear.

Q: Is this hand-written or typed?
A: This is a professional typed computer PDF. You can use it as a reference for your handwritten submission.