 MORE IN Data Structures Algorithm
SPPU Computer Engineering (Semester 3)
Data Structures Algorithm
December 2016
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 fromQ.1(a,b,c) and Q.2(a,b)
1(a) Define algorithm and its characteristics.
4 M
1(b) Write pseudo c/c++ code to perform simple transpose of sparse matrix. Discuss its time complexity.
6 M
1(c) Derive address calculation formula for one-dimensional array with one example.
2 M

2(a) Explain asymptotic notations-Big-O, Theta and omega with one example of each.
6 M
2(b) Write pseudo c/c++ code to perform polynomial multiplication using arrays.
6 M

Solve any one question fromQ3(a,b) and Q.4(a,b)
3(a) Write pseudo c/c++ code to represent doubly linked list as ADT.
6 M
3(b) Explain step by-step conversion using stack for given infix expression to postfix expression:
((a/(b-c+d)) * (e-a)*c
6 M

4(a) Write pseudo c/c++ code to implement stack as an ADT.
6 M
4(b) Write an alogrithm to perform the following operations on singly linked list:
1) Reverse
2) Sort.
6 M

Solve any one question fromQ5(a,b) and Q.6(a,b)
5(a) Write pseudo c/c++ code to represent deque and perform the following operations:
1) Create Deque
2) Insert
3) Delete
4) Diplay.
7 M
5(b) What is circular queue? Explain the advantages of circular queue ove linear queue
6 M

6(a) Write psedo c/c++ code to implement circular queue using arrays.
7 M
6(b) Explain applications of priority queue in detail.
6 M

Solve any one question fromQ7(a,b) and Q.8(a,b)
7(a) Explain quick sort and sort the given list using quick sort:
15, 08, 20, -4, 16, 02, 01, 12, 21, -2
6 M
7(b) Write an algorithm for Fibonacci search and findout time complexity.
7 M

8(a) Explain shell sort and sort the given list using shell sort:
08, 03, 02, 11, 05, 14, 00, 02, 09, 04, 20
6 M
8(b) write shorrt note on stability of sorting. Compare Heap sort Quick sort with one example and discuss time complexity.
7 M

More question papers from Data Structures Algorithm