Design and Analysis of Algorithms | IGNOU Master of Computer Applications (MCA_NEW) (MCA_NEW)

Download IGNOU MCA_NEW MCS-211 solved assignment for the January 2026 session — Design and Analysis of Algorithms. This paper contains 4 questions with 4 detailed solved answers including key points and references. Available in English. Free PDF download for Master of Computer Applications (MCA_NEW) students.

Back to MCS-211Back to MCS-211 Course Details

MCS-211—January 2026 / July 2026

Design and Analysis of Algorithms

AssignmentMaster of Computer Applications (MCA_NEW) (MCA_NEW)Computer Applications

Total Questions

Answers Available

With Sub-parts

Available

Answer Status

Questions & Answers

QQ1✓ AnswerLong Answer700 words

Answer all questions.

7 sub-questions

QQ2✓ AnswerLong Answer1000 words

Answer all questions.

5 sub-questions

QQ3✓ AnswerLong Answer1000 words

Consider the following Graph: Figure 1: A sample weighted Graph

5 sub-questions

QQ4✓ AnswerLong Answer800 words

Answer all questions.

4 sub-questions

Download Study Materials

Get all questions and answers in PDF for offline study.

Related Courses

All Courses

Back to MCS-211 All Master of Computer Applications (MCA_NEW) Courses

MCS-211 Assignment Questions — January 2026

QQ1. Answer all questions.

(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? (100 words)
(b)) Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times. (100 words)
(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. (100 words)
(d)) Explain the Big Theta (Θ) and Big Omega (Ω) 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, and Ω bounds for the following function: f(n)= 999n^3+999999n+100 (200 words)
(e)) Write the Right to Left binary exponentiation algorithm. Demonstrate the use of this algorithm to compute the value of 5^23. Show all steps of the computation. Explain the worst-case complexity of this algorithm. (200 words)
(f)) Write and explain the Insertion sort algorithm. Discuss its best and worst-case time complexity. (150 words)
(g)) What is a recurrence relations? When are they used? Solve the following recurrence relations using the Master's method: a. T(n) = 16T(n/4) + n² b. T(n) = 8T(n/2) + n² (150 words)

Key Points:

Sieve of Eratosthenes efficiently finds primes in O(N log log N).
Quadratic-time (O(n²)) grows as n-squared (e.g., Bubble Sort).
Exponential-time (O(2^n)) grows very rapidly (e.g., brute-force TSP).
Big Theta (Θ) provides tight asymptotic bounds (upper and lower).

Answer: (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? The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified limit. To find primes in the range 2 to 10000, we initialize a boolean array, `isPrime[0...10000]`, setting all entries from 2 onwards to true. We then iterate from `p = 2` up to `√10000` (which is 100). If `isPrime[p]` is true, `p` is a prime. We then mar...

QQ2. Answer all questions.

(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,..., p5) = (10, 20,18,15,5) (W1, W2,..., W5) = (2, 5, 3, 5, 1) (200 words)
(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 (200 words)
(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. (200 words)
(d)) Explain the divide and conquer approach of multiplying two large matrices of size 16 × 16. Compute the time complexity of this approach. (200 words)
(e)) Write and explain the algorithm of Topological sorting with the help of an example. Also, define the concept of strongly connected components in a directed Graph. (200 words)

Key Points:

Optimization problems seek to maximize/minimize an objective function subject to constraints.
Greedy algorithms make locally optimal choices, aiming for a global optimum (e.g., Fractional Knapsack).
Huffman coding assigns shorter codes to frequent characters for optimal data compression.
Quick Sort's PARTITION algorithm rearranges elements around a pivot, recursively sorting sub-arrays.

Answer: This comprehensive response addresses key algorithms and data structures from the MCS-211 course, focusing on optimization, greedy approaches, sorting, divide-and-conquer strategies, and graph theory concepts. It explains mathematical representations of problems, step-by-step algorithm demonstrations, and complexity analysis, ensuring a thorough understanding of the topics. Each sub-question is tackled individually, providing detailed explanations, practical examples, and computational steps as...

QQ3. Consider the following Graph: Figure 1: A sample weighted Graph

(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. (200 words)
(b)) Write the Bellman-Ford shortest path algorithm. What is the time complexity of this shortest path algorithm? Find the shortest paths from the vertex 'A' using Bellman-Ford's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation. (200 words)
(c)) Write the algorithm to find the Optimal Binary Search Tree. Demonstrate this algorithm to find the Optimal Binary Search Tree for the following probabilities of 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) i 0 1 2 3 4 Pi 0.15 0.05 0.15 0.25 qi 0.10 0.05 0.05 0.10 0.10 (300 words)
(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 (100 words)
(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. (200 words)

Key Points:

Kruskal's algorithm builds MST by adding smallest non-cycling edges, uses DSU, O(E log E) time.
Prim's algorithm builds MST by adding smallest edge from MST to non-MST vertex, uses Min-PQ, O(E log V) time.
Bellman-Ford finds shortest paths in weighted digraphs, handles negative weights, detects negative cycles, O(VE) time.
Optimal Binary Search Tree (OBST) uses dynamic programming to minimize expected search cost, O(n³) time.

Answer: This document provides comprehensive answers to the five sub-questions based on the Design and Analysis of Algorithms course (MCS-211). Each sub-question addresses a fundamental algorithm, including its definition, time complexity, and step-by-step demonstration using suitable examples, adhering to the specified word limits and formatting guidelines. Detailed solutions for each part are presented in the `subAnswers` array.

QQ4. Answer all questions.

(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 (200 words)
(b)) What are NP and NP-Complete classes of problems? Explain with the help of at least two examples each. (200 words)
(c)) Define the relationship between P, NP, NP-Complete and NP-Hard classes of problems. How are they different from each other. (200 words)
(d)) Describe the following Problems: (i) 3-CNF SAT Problem (ii) 0/1 Knapsack Problem (iii) Vertex Cover Problem (iv) Graph colouring problem (400 words)

Key Points:

Intractable problems cannot be solved in polynomial time; computational cost grows exponentially.
Traveling Salesman Problem (TSP) is finding the shortest tour visiting all cities, an NP-Hard problem.
NP class problems have solutions verifiable in polynomial time, though finding them may be hard.
NP-Complete problems are the hardest in NP, polynomially reducible from all other NP problems.

Answer: Computational complexity theory categorizes problems based on the resources (time, space) required to solve them. This question delves into these classifications, specifically focusing on intractable problems and the relationships between P, NP, NP-Complete, and NP-Hard classes, alongside detailed explanations of key problems like TSP, Clique, 3-CNF SAT, 0/1 Knapsack, Vertex Cover, and Graph Colouring. Understanding these concepts is crucial for algorithm design, as it helps determine whether an...

Design and Analysis of Algorithms | IGNOU Master of Computer Applications (MCA_NEW) (MCA_NEW)

Back to MCS-211Back to MCS-211 Course Details

MCS-211—January 2026 / July 2026

Design and Analysis of Algorithms

AssignmentMaster of Computer Applications (MCA_NEW) (MCA_NEW)Computer Applications

Total Questions

Answers Available

With Sub-parts

Available

Answer Status

Questions & Answers

QQ1✓ AnswerLong Answer700 words

Answer all questions.

7 sub-questions

QQ2✓ AnswerLong Answer1000 words

Answer all questions.

5 sub-questions

QQ3✓ AnswerLong Answer1000 words

Consider the following Graph: Figure 1: A sample weighted Graph

5 sub-questions

QQ4✓ AnswerLong Answer800 words

Answer all questions.

4 sub-questions

Download Study Materials

Get all questions and answers in PDF for offline study.

Related Courses

All Courses

Back to MCS-211 All Master of Computer Applications (MCA_NEW) Courses

MCS-211 Assignment Questions — January 2026

QQ1. Answer all questions.

(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? (100 words)
(b)) Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times. (100 words)
(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. (100 words)
(d)) Explain the Big Theta (Θ) and Big Omega (Ω) 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, and Ω bounds for the following function: f(n)= 999n^3+999999n+100 (200 words)
(e)) Write the Right to Left binary exponentiation algorithm. Demonstrate the use of this algorithm to compute the value of 5^23. Show all steps of the computation. Explain the worst-case complexity of this algorithm. (200 words)
(f)) Write and explain the Insertion sort algorithm. Discuss its best and worst-case time complexity. (150 words)
(g)) What is a recurrence relations? When are they used? Solve the following recurrence relations using the Master's method: a. T(n) = 16T(n/4) + n² b. T(n) = 8T(n/2) + n² (150 words)

Key Points:

Sieve of Eratosthenes efficiently finds primes in O(N log log N).
Quadratic-time (O(n²)) grows as n-squared (e.g., Bubble Sort).
Exponential-time (O(2^n)) grows very rapidly (e.g., brute-force TSP).
Big Theta (Θ) provides tight asymptotic bounds (upper and lower).

QQ2. Answer all questions.

(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,..., p5) = (10, 20,18,15,5) (W1, W2,..., W5) = (2, 5, 3, 5, 1) (200 words)
(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 (200 words)
(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. (200 words)
(d)) Explain the divide and conquer approach of multiplying two large matrices of size 16 × 16. Compute the time complexity of this approach. (200 words)
(e)) Write and explain the algorithm of Topological sorting with the help of an example. Also, define the concept of strongly connected components in a directed Graph. (200 words)

Key Points:

Optimization problems seek to maximize/minimize an objective function subject to constraints.
Greedy algorithms make locally optimal choices, aiming for a global optimum (e.g., Fractional Knapsack).
Huffman coding assigns shorter codes to frequent characters for optimal data compression.
Quick Sort's PARTITION algorithm rearranges elements around a pivot, recursively sorting sub-arrays.

QQ3. Consider the following Graph: Figure 1: A sample weighted Graph

(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. (200 words)
(b)) Write the Bellman-Ford shortest path algorithm. What is the time complexity of this shortest path algorithm? Find the shortest paths from the vertex 'A' using Bellman-Ford's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation. (200 words)
(c)) Write the algorithm to find the Optimal Binary Search Tree. Demonstrate this algorithm to find the Optimal Binary Search Tree for the following probabilities of 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) i 0 1 2 3 4 Pi 0.15 0.05 0.15 0.25 qi 0.10 0.05 0.05 0.10 0.10 (300 words)
(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 (100 words)
(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. (200 words)

Key Points:

Kruskal's algorithm builds MST by adding smallest non-cycling edges, uses DSU, O(E log E) time.
Prim's algorithm builds MST by adding smallest edge from MST to non-MST vertex, uses Min-PQ, O(E log V) time.
Bellman-Ford finds shortest paths in weighted digraphs, handles negative weights, detects negative cycles, O(VE) time.
Optimal Binary Search Tree (OBST) uses dynamic programming to minimize expected search cost, O(n³) time.

QQ4. Answer all questions.

(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 (200 words)
(b)) What are NP and NP-Complete classes of problems? Explain with the help of at least two examples each. (200 words)
(c)) Define the relationship between P, NP, NP-Complete and NP-Hard classes of problems. How are they different from each other. (200 words)
(d)) Describe the following Problems: (i) 3-CNF SAT Problem (ii) 0/1 Knapsack Problem (iii) Vertex Cover Problem (iv) Graph colouring problem (400 words)

Key Points:

Intractable problems cannot be solved in polynomial time; computational cost grows exponentially.
Traveling Salesman Problem (TSP) is finding the shortest tour visiting all cities, an NP-Hard problem.
NP class problems have solutions verifiable in polynomial time, though finding them may be hard.
NP-Complete problems are the hardest in NP, polynomially reducible from all other NP problems.

MCS-211 Solved Assignment — January 2026 / July 2026

Design and Analysis of Algorithms | IGNOU Master of Computer Applications (MCA_NEW) (MCA_NEW)

MCS-211—January 2026 / July 2026

Design and Analysis of Algorithms

Questions & Answers

Download Study Materials

Related Courses

MCS-211 Assignment Questions — January 2026

QQ1. Answer all questions.

QQ2. Answer all questions.

QQ3. Consider the following Graph: Figure 1: A sample weighted Graph

QQ4. Answer all questions.

More MCS-211 Solved Materials

MCS-211 Solved Assignment — January 2026 / July 2026

Design and Analysis of Algorithms | IGNOU Master of Computer Applications (MCA_NEW) (MCA_NEW)

MCS-211—January 2026 / July 2026

Design and Analysis of Algorithms

Questions & Answers

Download Study Materials

Related Courses

MCS-211 Assignment Questions — January 2026

QQ1. Answer all questions.

QQ2. Answer all questions.

QQ3. Consider the following Graph: Figure 1: A sample weighted Graph

QQ4. Answer all questions.

More MCS-211 Solved Materials