 MORE IN Data Structures Algorithm
SPPU Computer Engineering (Semester 3)
Data Structures Algorithm
May 2017
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question from Q.1(a,b,c) &Q.2(a,b,c)
1(a) Show that f(x) = 0 (x3) if function f(x) is defined as $f(x) = 5x^{3}+6x^{2}+1$
3 M
1(b) Differentiate between linear and non-linear data structure with example.
3 M
1(c) Explain divide and conquer strategy with example. Also comment on the time analysis.
6 M

2(a) Explain fast Transpose of sparse matrix with suitable example. Discuss time complexity of fast transpose.
6 M
2(b) Explain polynomial representation using arrays with suitable example.
3 M
2(c) Derive recurrence relation to represent set of natural numbers giving remainder one when divided by three.
3 M

Solve any one question from Q.3(a,b,c) & Q.4(a,b,c)
3(a) Represent the following polynomial by using-generalized linked list:
(a, b, (c, d (e, g,), h) (f))
3 M
3(b) Write an algorithm for postfix evaluation with suitable example.
6 M
3(c) Write a pseudo C code to reverse singly linked list.
3 M

4(a) Convert the following prefix expression into postfix * + a - bc / - de + -fgh
3 M
4(b) Write an algortihm to convert infix expression to postfix expression.
6 M
4(c) Write an algorithm to delete intermediate node from Doubly linked list.
3 M

Solve any one question from Q.5(a,b) & Q.6(a,b)
5(a) What is circular queue? Explain the advantages of circular queue over linear queue.
6 M
5(b) Write pseudo C/C++ code to represent queue as an ADT.
7 M

6(a) Explain array implementation of priority queue with all basic operations.
6 M
6(b) Write pseudo C/C++ code to implement circular queue using linked list.
7 M

Solve any one question from Q.7(a,b) &Q.8(a,b)
7(a) Explain quick sort and sort the given list using quick sort:
39, 09, 81, 45, 90, 27, 72, 18
6 M
7(b) Write an algorithm for binary search. Derive recurrence relation and find out time complesity of the search.
7 M

8(a) Explain heap sort and sort the given list using heap sort:
08, 03, 02, 11, 05, 14, 00, 02, 09, 04, 20.
6 M
8(b) Write a short note an stability of sorting. Compare bubble sort, insertion sort and selesction sort with one example and discuss time complexity.
7 M

More question papers from Data Structures Algorithm