# Computer Science(Dec 2010)

Note : Attempt any five questions All questions carry equal marks.          „

Unit—I

1.  (a) What are- Asymptotic notations ? Explain each

notation with example and diagram.                                  12

(b) Solve the following recurrence relation X(n) = t (n – 1) + 1, with T(0) = 0 as initial condition. Also find big oh notation.                                                                          8

Or                                       /

1.  (a) What is recursion ? How does it differ from iteration ?

Write an algorithm to generate first ten Fibonacci numbers recursively. . <          ^

(b) Consider a 2D array declared in “C” A  . Element type is integer. If the base address is 1076, what will be the address of A   ? Memory’ is

O

byte oriented.

P. T. O.

[ 2 3                                    CS/IT-305(N)

Unit-II

. ✓ »

1.  (a) Explain the inserting and deleting node from linked

list implementing stack and queue.                                          16

(b) What are D-queue and priority queue ?                                      4

‘                                                                                                                                                                                                                                              Or

1.  (a) Write an algorithm to convert infix to postfix

expression. Explain with example.                                           10

(b) Write function for :                                                                   10

(i)     Finding size

(ii)   Checking empty

(iii)                                                                                                                       Checking full  .           –

for the implementation of a queue in circular array with index values to indicate emptiness.

Unit-III

1.  (a) Following nodes are insert into empty tree in order

” . 12 5, 16,22,45,2, 10, 18,30,50, 12, 1

Construct : r <                                                                                                                     ■                   .

(i)     Binary Search Tree

(ii)   AVL Tree

(b) Draw the order-5 B-tree resulting from inserting the following keys (in th’l order) into an initially empty tree :                                       —                                     8

4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, ’77, 39, 12        ;

c                                                                            Or                             .       .

1.  (a) Explain the operation of AVL Tree.                                                                                                                     8

(b) Write, an algorithm to delete operation in any binary search tree (Taking all cases).          12

Unit -IV

. (a) Compare the worst case performance of heap sort with

the worst case performance and average case of quick

10

sort.

(b) Explain insertion sort and selection sort brietly. 10

Or

1.  (a) What is the difference between an index function ana

a hash function ? Explain three techniques to built the

. 10 hash function.

(b) Explain how balance is restored when an insertion into – – height-balanced tree puts a code out of balance ? 10 . Unit-V

1.  -(a) Apply Prim’s algorithm to find the minimum spanning

tree of the given graph.

Display the tree at each stage.                                         „

(b) Compare graph traversal techniques.

Or

f

1. (a) Explain Dijkstra algorithm with suitable example. 10 (b) Write short notes on the following :       5                                                                                      each

(i)        Strongly connected graph

 17,660

(ii)      Sparse matrix