Data Structure And Algorithm
Note : Attempt any 5 questions. Each question carries equal marks.
1 (a) Write and algorithm to perform push and pop operation on the stack.
(b) Write recursive definition and recursive algorithm to generate first 50 terms of the fibonacci series.
2.(a) What is Towers of Hanoi Problem? Give the recursive solution of this problem for 3-disk at the source peg.
(b) What are the advantaes of double linked list over singly linked-list? Write an algorithm to delete a node from the singly linked-list.
3.(a) Explain the following :
(i) Sparse Matrices
(ii) Threaded binary tree
(b) What is tail recursion? Explain with the help of a suitable example.
4.(a) Write algorithm to transform an expression from prefix to postfix. Also, clearly mention the assumptions if any regarding the input. Discuss the time and space complexities for your algorithm.
(b) Give recursive and iterative definition to generate the first 50 prime numbers.
5.(a) Discuss the complexities with examples in terms of the following notation
(i) Big O (ii) theta (iii) ohm
(b) Which of the searching algorithms is suitable for searching an element from an unsorted array of elements? Write the algorithm for the same.
6.(a) Apply binary search algorithm to pick an element 21 from the following array of elements:
(b) Deduce the reccurrence relation for the solution of Towers of Hanoi problem for N-disks.
7.(a) Draw a binary tree which labels a,b,c,d,e,f and for which 'Inorder' and 'Postorder' traversal results in the following sequences :
(i) in order : a,f,b,c,d,g,e
(ii) post order : a,f,c,g,e,d,b
(b) State 8-queen problem. Use the concept of back tracking to solve it. Also, write the algorithm for the same.
8. Write short notes on any two of the following :
(a) Sorting technique
(c) BFS and DFS
(i) Artificial Intelligence
(ii) Systems Programming
(b) Discuss briefly how imperative paradigm is different from functional paradigm conceptually. How does this bring difference in language following the two paradigms programmatically?
2 (a) Discuss the binding times with respect to design, compilation and execution.
(b) Differentiate between early and late binding. Also explain advantages and disadvantages of each.
3 (a) What is a data object? Classify them on the basis of different concepts.
(b) Write specifications and implementation for a record structured object.
4 (a) List and explain all kinds of arrays that you know, clearly showing their use in different requirements.
(b) What do you understand by implicit and no declaration? Explain them in detail mentioning how the languages providing support for them would to type checking.
5 (a) Discuss mechanism for subprogram sequence control clearly showing the use of activation record and CIP and CEP.
(b) What do you understand by function attaining first class citizen status in a functional language? Explain in detail showing the use of higher order functions.
6 (a) Discuss and explain the various evaluation strategies which a language may adopt.
(b) What do you understand by parameter transmission? Differentiate between call by value and call by reference parameter transmission methods.
7 (a) Why do oops paradigm give importance to inheritance and polymorphism? Discuss explaining them and their importance.
(b) Write short notes on the following :
(i) GUI and CUI programming
(ii) Implementation of an integer date object by language