MCS 031 Notes

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.
Also available:-
BCA all semester new solved assignments Download
BCA all semester new revised books/blocks,study materials Download
MCA all semester new solved assignments Download
MCA all semester new revised books/blocks,study materials Download
BCA all semester term-end exam notes,important questions,guess papers (june-

december) Download
MCA all semester term-end exam notes,important questions,guess papers (june-

december) Download
BCA/MCA asp.net project Download

MCS 031 Notes

Uploaded by

Copyright:

Available Formats

MCS 031 Notes

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MCS 031 Notes

Uploaded by

Copyright:

Available Formats

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

ANALYSIS OF ALGORITHMS) books/block,term-end exam notes,upcoming

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

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

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

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

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

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

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

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

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

BCA all semester new revised books/blocks,study materials Download

MCA all semester new solved assignments Download

MCA all semester new revised books/blocks,study materials Download

BCA all semester term-end exam notes,important questions,guess papers (june-

MCA all semester term-end exam notes,important questions,guess papers (june-

BCA/MCA asp.net project Download

You might also like