# Computer Science(Dec 2013)

Note: Total no. of questions 10. Attempt one question (including all parts) from each unit. All questions carry equal marks.

Unit-I

1.  a) What do you mean by algorithm complexity? Discuss a

priori analysis and posteriori testing of an algorithm.

b) Explain different nonprimitive data structures and the operations associated with them.

OR

1.  a) Write an algorithm to obtain the sum of the first ten terms

ofthe following series using recursion. Also give iterative algorithm.

Unit-II

 PTO
1. a) Write a function that creates a new linear linked lists by selecting alternate elements of a given linear linked list.

CS/1T-305

b) Convert the following expressions into postfix and prefix form.

i)     (A + B)*c/D+El-FftG

ii)  B*(-C)*D + A”tD

OR

1.  a) Explain the following:

i)     Multiple stacks

ii)  D-quetfe

iii)                       Multidimensional array.

b) Discuss about the implementation of fixed size block and variable size block dynamic memory allocation.

Unit-III

multilist representations of the following graph.

b) Create B Tree of order 5 from the following lists of data items : 20, 30,40, 10, 5, 40, 50, 60, 55, 65.

 PTD

OR

r,<3/IT_’UK

 6. a) What is threaded binary tree? Explain, and create the threaded binary tree for the given tree.

b) Write the recursive Inorder, Preorder and Postorder tree traversal algorithms.

Unit-FV

1.  a) Compare merge sort and quick sort algorithms in terms

of storage space and time required to execute them.

b) What is min heap? Create the min heap for the given data set:

1. 15, 50,3, 33,45,40. 80, 80, 10

OR

1.  a) What are the different types of search techniques? Explain

the one which is more efficient among them.

b) Explain the following:

i)     Symbol table

ii)  Hash table

iii)                       Dynamic tree table.

Unit-V

1.  a) Write an algorithm to find all the connected components

of a graph. Also give the time analysis ofyour algorithm.

hta

b) Define the terms.

i)      Edge and vertices

ii)   Acyclic graph

iii ) Degree of a graph

iv)         Path and circuit.

OR

1. Consider the given graph :