**IGNOU BCA/MCA all semester new revised (1st semester,2nd semester,3rd semester,4th**

**semester,5th semester and 6th semester) solved assignments,term-end exam notes,study materials,important**

**questions,books/blocks (June-December) free download.**

**IGNOU MCA MCS-031 3rd semester term-end examination (**

**DESIGN AND ANALYSIS OF**

**ALGORITHMS) books/block,term-end exam notes,upcoming guess paper,important questions,study materials,previous year papers download.**

**Notes-1**

1. (a) (i) Solve the recurrence equation T(n) = 2.T(n/4) + n3 for n > 1 and T(1) = 1.

Obtain the asymptotic upper bound for f(n) = (6n2-5n + 2)2.

(b) A binomial coefficient is defined by the following recurrence relation :

C(n, 0) = 1 and C(n, n) = 1 for n > 0.

C(n, k) = C(n-1, k) + C(n-1, k-1) for n>k> O.

(i) Draw the recursion tree for C(6, 4).

(ii) Write a recursive function to generate C(n, k).

(iii) Give an algorithm based on Dynamic Programming to solve C(n, k).

(iv) Compare the time and space requirements of the algorithm in part (iii).

(c) (i) You are given currency of denominations {500, 100, 50, 20, 10, 5}.Give a greedy algorithm to obtain the minimum number of denomination for any amount which is a multiple of 5.

(ii) Write a procedure to merge two -sorted arrays. Analyze the running time of your algorithm.

(d) Is the following sequence a heap ? If not,convert it into a heap.

< 10, 5, 3, 8, 6, 1, 7 >

2. (a) (i) Write an algorithm to find the ith smallest element in O(n) time.

(ii) Illustrate the working of your algorithm on the input < 1, 5, 8, 6, 13, 4, 3 > to find the 4th smallest element.

(b) (i) Define a BFS tree. Give the breadth first traversal for the undirected graph given below, starting from vertex 'a'.

(ii) Give any two applications of Depth first search.

3. (a) (i) Explain Dijkstra's shortest path algorithm.

(ii) Find the shortest path in the following graph represented by adjacency matrix, from vertex 'a'.

(b) (i) Explain the principle of greedy algorithm.

(ii) Explain Prim's algorithm for Minimum Spanning Tree, and obtain the MST for the graph in question 3 (a) (ii).

4. (a) (i) Define Finite Automata and Regular Expression.

(ii) Write Regular Expression for the following :

(1) L = (01)n,≥1.

(2) Strings that start with '1' and end with '0'.

(b) Obtain the CFG for the following :

(i) Strings of matching parenthesis.

(ii) Expression of the form E = (E + E) * E.The expression contains : parenthesis,operators : +, -,* and /.

5. (a) Explain the class-P, NP and NP-complete problems.

(b) (i) What is undecidability ? Give an example for an undecidable problem.

(ii) Design a polynomial time reduction from the vertex cover problem to the clique problem.

**Notes-2**

1. (a) Write recursive binary search algorithm and analyse its run time complexity.

(b) Solve the recurrence :

T(n) = 2T (n/2) + n; n ≥ 2= 1 ;n<2.

(c) Using Dijkstra's algorithm, find the minimum distances of all the nodes from source node 'a' for the following graph :

(d) Construct a Turing Machine (TM) to accept all languages of palindromes on alphabet ∑= (a, b).

(e) Explain matrix multiplication using dynamic programming.

(f) What is minimax principle ? Explain with the help of an example.

2. (a) Obtain the minimum cost spanning tree for the following graph using Prim's algorithm.

(b) Obtain the DFS tree for the graph given in Q.no. 2(a); considering node '

**a'**as root node.
(c) Explain the Chomsky's classification of grammars.

3. (a) Enumerate any five well-known techniques for designing algorithms for solving problems.

(b) Sort the following elements using Heap Sort :

10, 28, 46, 39, 15, 12, 18, 9, 56, 2.

Show each step, while creating a heap and processing a heap.

(c) For any set S of strings prove that S* = (S*)* = S**.

4. (a) Arrange the following growth rates in increasing order :

O(n3), O(3n), O(n log n), O(1), O(log n).

(b) For the function f(x) = 4x3 + 6x + 5,show that (i) f(x) = O(x4) but (ii) x4 ≠ O(f(x)).

(c) What is Pushdown Automata (PDA) ? Build a PDA that accepts the language even palindrome.

5. (a) What is Satisfiability problem ? Explain briefly.

(b) Prove that the running time of binary search algorithm in worst case is O(log2 n).

(c) Using Bubble Sort, sort the following sequence in increasing order :

11, 21, 6, 14, 8, 12, 28, 32.

(d) Write a note on regular languages.

**Notes-3**

1. (a) What is big O notation ? How is it different from 𝛀 notation ?

(b) Give an analysis of merge-sort. For simplicity, assume that the number of elements i.e. n is an exact power of two.

(c) Explain limitations of Strassen's Algorithm for matrix multiplication.

(d) Use Master's method to find tight asymptotic bounds for the following recurrence :

T(n) T (n/2)+n

(e) Give a divide and conquer based algorithm to find ith largest element in an array of size n.

(f) What is regular expression ? Write a regular expression over ∑= {a, b} to generate all

string that start with a and end with two b's.

(g) Write binary search algorithm and evaluate its time complexity in the best, average and worst cases.

(h) Explain NP- complete problem with the help of an example.

2. (a) Find the topological ordering of the following graph :

(b) Write Kruskal's algorithm and determine its time complexity.

(c) Represent the following graph using

(i) Array ; and (ii) Adjancy List

3. (a) Sort the given list using bubble sort and show the steps involved in the process :

2, 7, 5, 10, 21, 3

(b) Write Euclid's algorithm for finding Greatest Common Divisor (G.C.D) of two natural numbers m and n.

(c) What is the benefit of preconditioning a problem space ? Explain using an example.

(d) Consider the CFG :

S→SS |XaXaX|∧

X→ bX|/∧

Explain the language generated by this CFG

4. (a) What is Push Down Automata ? How is it different from Finite Automata.

(b) What is MinMax Algorithm ? Explain how Alpha-Beta pruning helps in improving MinMax algorithm.

(c) What is best case analysis ? Perform the best case analysis for Quick Sort.

5. (a) Explain each of the following, with an appropriate example :

(i) NIM/ Marienbad Game

(ii) Principle of Mathematical Induction

(iii) Halting Problem

(b) Trace how Depth First Search Traverses the following tree, when starting at node A.

IGNOU MCA MCS-031 3rd semester term-end examination (DESIGN AND ANALYSIS OF

ALGORITHMS) term-end exam notes

**Download**

**Also available:-**

**BCA/MCA asp.net project**

**Download**