Download Model question papers & previous years question papers
|
Posted By: S.Yamini Member Level: Diamond Posted Date: 04 May 2008
|
2006 Indira Gandhi National Open University (IGNOU) M.C.A Design and Analysis of Algorithms Question paper
|
|
|
Term-End Examination
MCS031: Design and Analysis of Algorithms
Time: 3 hours
Maximum Marks: 100
Note : Question number 1 is compulsory. Attempt any three questions from the rest. All algorithms should be written nearer to C/C++ language
1. (a) (i) Give an array of 8 elements which is the best case for Insertion Sort.
(ii) Give an array of 8 elements which is the worst case for Insertion Sort.
The best/worst case(s) should be according to the number of insertions into the array that require a shift of one or more elements. In each of the above cases, count the number of shifts. (6)
(b) Arrange the following in order of best to worst efflciency:
O(n2 log n), O(n2), O(n3), O(n2 log vn). (4)
(c) Give an analysis of worst case running time of quicksort. When does it occur? How can we improve the worst case performance of quicksort? (10)
(d)Discuss how depth first search can be used to find cycles in an undirected graph. (5)
(e) what do we understand by the "optimal substructure property'" in a dynamic programming problem? (5)
(f) Describe "semidecidability" of a Turing Machine. (5)
(g) How do we establish that a problem is NP-Complete? (5)
2. (a)write a recursive algorithm to reverse a singly linked list. (5)
(b) Prove that the lower bound for the number of comparisons in any comparison sort (e.g. HeapSort or QuickSort or MergeSort) is O (n lg n). [where lg means 1og2] (10)
(c) what is the difference between a pure recursive solution and a dynamic prograrnming solution to a problem? (5)
3. (a) what is the importance of generating alpha or beta value for a node alpha-beta procedure? which player among MIN and MAX uses alpha value and which player uses beta value, and, how? (8)
(b) Describe the sequence of steps involved in the designing of a greedy algorithm. (6)
(c) Write the context free grammar for a non-null even palindrome. (6)
4. (a) (i) Construct a non-deterministic Finite Automata (NDFA) representing the language: (5)
(ab)* (ba)* + aa*
(ii) Construct a Finite Automata for the language: (5)
a* (ab + ba) b*
(b) Design a Turing machine that shifts a string on the tape, one place to the right, i.e., it transforms #w# to ##ww# where 'w' is a string with no blanks, # represents a blank square and the underlined symbol represents the current position of the head. (8)
(c) Define "Pumping Lemma" for Context Free Grammars. (2)
5. (a) Find whether the following two boolean expressions are satisfiable or not: (6)
(i) P ? (? P ? Q ? R)
(ii) Q ? (? Q ? P ? (Q ? P))
(b) Among "best first search" and "depth first search", which technique is used in inorder traversal of a Binary Tree and how? (4)
(c) Show how Breadth First Search algorithm works on the graph below. Assume that the vertices are considered in an alphabetical order and that the graph is represented using adjacency list representation in which each adjacency list is ordered alphabetically. Show that the queue operations for each step and the distance calculated for each vertex start from the vertex 'A'. (10)
== Diagram ==
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.