Bought By: 2953

Rating:

Get Good Marks in your **MCA (Revised) Computer Application** Programme in the Term-End Exams even if you are busy in your job or profession.

We've sold over 52,426,951 Help Books and Delivered 65,315,395 Assignments Since 2002.

As our customers will tell you...yes, it really result-oriented.

- University IGNOU (Indira Gandhi National Open University)
- Title Design and Analysis of Algorithms
- Language(s) English
- Code MCS-211
- Subject Computer Application
- Degree(s) MCA (Revised)
- Course Core Courses (CC)

- Unit 1 - Basics of an Algorithm and its Properties
- Unit 2 - Asymptotic Bounds
- Unit 3 - Complexity Analysis of Simple Algorithms
- Unit 4 - Solving Recurrences

- Unit 1 - Greedy Technique
- Unit 2 - Divide and Conquer Technique
- Unit 3 - Graph Algorithm-I

- Unit 1 - Graph Algorithms-II
- Unit 2 - Dynamic Programming Technique
- Unit 3 - String Matching Algorithms

- Unit 1 - Introduction to Complexity Classes
- Unit 2 - NP-Completeness and NP-Hard Problems
- Unit 3 - Handling Intractability

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.

Buy MCS-211 Assignment - MCS-214 Professional Skills and Ethics
- MCS-215 Security and Cyber Laws
- MCS-218 Data Communication and Computer Networks
- MCS-219 Object Oriented Analysis and Design
- MCS-220 Web Technologies
- MCS-221 Data Warehousing and Data Mining
- MCS-224 Artificial Intelligence and Machine Learning
- MCS-225 Accountancy and Financial Management
- MCS-226 Data Science and Big Data
- MCS-227 Cloud Computing and IoT
- MCS-230 Digital Image Processing and Computer Vision
- MCS-231 Mobile Computing

To attend IGNOU MCS-211 Term-End Examination, you must first submit your Assignments to the university and it is possible from the MCS-211 study material. You can solve all necessary Assignments using Help Books. This will help in gaining good marks.

All best wishes with our efforts that you do not meet any obstacle before attending examinations next year. You can pass the MCA (Revised) Computer Application Programme Annual Exams with a good grade using Books/Materials from any one place at home or anywhere else!

ALL THE BEST!!!

**Team GullyBaba**