IGNOU MCS-211
- Design and Analysis of Algorithms,
Latest Solved Assignment
(January 2024 - July 2024)

Q1: a) Develop an efficient algorithm to find a list of prime numbers from 100 to 1000.

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

c) Using Horner's rule, evaluate the polynomial p(x)= 2x5-5x4-3x2+15 at x=2. Analyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.

d) State and explain the theorems for computing the bounds O, Ω and Θ. Apply these theorem to find the O-notation, Ω-notation and Θ-notation for the function: 𝑓(𝑛)= 10𝑛3 +18𝑛2 +1

e) Explain binary exponentiation for computing the value 519. Write the right-toleft binary exponentiation algorithm and show its working for the exponentiation 519. Also, find the worst-case complexity of this algorithm.

f) Write and explain the linear search algorithm and discuss its best and worstcase time complexity. Show the working of the linear search algorithm for the data: 12, 11, 3, 9, 15, 20, 18, 19, 13, 8, 2, 1, 16.

g) What is a recurrence relation? Solve the following recurrence relations using the Master’s method

Q2: a) What is a Greedy Approach to Problem-solving? Formulate the fractional Knapsack Problem as an optimisation problem and write a greedy algorithm to solve this problem. Solve the following fractional Knapsack problem using this algorithm. Show all the steps.
Suppose there is a knapsack of capacity 15 Kg and 6 items are to packed in it. The weight and profit of the items are as under:
(p1, p2,…, p6) = (3, 2, 4, 5, 1, 6)
(w1, w2,…, w6) = (2, 1, 2, 1, 5, 1)

b) What is the purpose of using Huffman Codes? Explain the steps of building a huffman tree. Design the Huffman codes for the following set of characters and their frequencies: a:15, e:19, s:5, d:6, f:4, g:7, h:8, t:10.

c) Expalin the Partition procedure of the Quick Sort algorithm. Use this procedure and quick sort algorithm to sort the following array of size 8: [12, 9, 17, 15, 23, 19, 16, 24]. Compute the worst case and best case complexity of Quick sort algorithm.

d) Explain the divide and conquer apprach of multiplying two matrices of large size. Also, explain the Strassen’s matric multiplication algorithm. Find the time complexity of both these approaches.

e) What is the use of Topological sorting? Write and explain the Topological sorting algorithm. Also, compute the time complexity for the topological sorting algorithm.

Q3: Consider the following Graph:

a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost spanning tree of the graph given in Figure 1. Show all the steps of computation. Also, compute the time complexity of both the algorithms.

b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest path algorithm. Show all the steps of computation. Also, find the time complexity of the algorithm.

c) What is dynamic programming? What is the principle of Optimality? Use the dynamic programming approach to find the optimal sequence of chain multiplication of the following matrices:

d) Make all the possible Binary Search Trees for the key values 25, 50, 75.

e) Explain the Knuth Morris Pratt algorithm for string matching. Use this algorithm to find a pattern “algo” in the Text “From algae to algorithms”. Show all the steps. What is the time complexity of this algorithm.

Q4: a) What are decision problems and Optimisation problems? Differentiate the decision problems and Optimisation problems with the help of at least two problem statements of each.

b) Define P and NP class of Problems with the help of examples. How are P class of problem different from NP class of Problems.

c) What are NP-Hard and NP-Complete problem? What is the role of reduction? Explain with the help of an example.

d) Define the following Problems:

(i) 3-CNF SAT
(ii) Clique problem
(iii) Vertex cover problem
(iv) Graph Colouring Problem

Q1. a) Develop an efficient algorithm to find a list of all the prime numbers up to anumber n (say 100).
b) Explain the following types of problems in Computer Science with the help of an example problem for each:
i) Searching
ii) String Processing
iii) Geometric Problems
iv) Numerical Problems

Q2. a) Using induction prove that, for all positive integers n,

b) What is the purpose of asymptotic analysis? What are the drawbacks of asymptotic analysis? Explain the Big-O notation with the help of an example.

Q3. a) Evaluate the polynomial p(x)= 5x 5+4x 4 -3x 3 -2x2+9x+11 at x=3 using Horner’s rule. Analyse the computation using Horner’s rule against the Brute force method of polynomial evaluation.
b) Write the linear search algorithm and discuss its best case, worst case and average case time complexity. Show the best case, worst case and the average case of linear search in the following data: 13, 15, 2, 6, 14, 10, 8, 7, 3, 5, 19, 4, 17.

Q4. a) Find an optimal solution for the knapsack instance n=7 and maximum capacity (W) =15,
(p1,p2,…,p6)=(4,5,10,7,6,8, 9)
(w1,w2,…, w6)=(1,2,3,6,2,4, 5)
b) Make an optimal Huffman tree and design the Huffman code for the following set of frequencies:a:7, e:6, s:20, d:2, f:1, g:3, h:4, t:7.

Q5. a) Write and explain the recursive binary search algorithm. Use this algorithm for searching an element in a sorted array of 7 elements.
b) Analyse the Quick sort algorithm using Master Method. Also draw the relevant recursion tree.
c) Write the algorithm for the divide and conquer strategy for Matrix multiplication. Also, analyse this algorithm.

Q6. a) Write the adjacency list and draw ADJACENCY MATRIX for the graph given below.

b) Write and explain the algorithm of Topological sorting. How can you compute time complexity for topological sorting?

Q7. a) Explain the working of Prim’s algorithm for finding the minimum cost spanning tree with the help of an example. Also find the time complexity of Prim’s algorithm.
b) Explain the working of Bellman-Ford algorithm for finding the shortest path from a single source to all destinations with the help of an example. Also find the time complexity of this algorithm.

Q8. a) Explain the process of creating a optimal binary search with the help of an example.
b) Find an optimal parenthesizing of a matrix-chain product who sesequence of dimensions is as follows:

Q9. a) Using the Rabin Karp algorithm, find the pattern string in the given text. Pattern: “ten”, Text: “attainthtenbetan”. Write all the steps involved.
b) Differentiate between Knuth Morris Pratt and Naïve String matching Algorithm

Q10. Differentiate between the following with the help of an example of each:

(i) Optimization and Decision Problems
(ii) P and NP problems

Q11. What are NP Hard and NP complete problems? Explain any one problem of each type.

Q12 Explain backtracking; and Branch and Bound techniques with the help of an example each.