Dsa- Answer Key

BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI DISTANCE LEARNING PROGRAMMES DIVISION BITS-TECH M Collaborative Programme: MS in Software Engineering SECOND SEMESTER 2008-2009 COURSE NO. COURSE TITLE Nature of Exam Duration Date of Exam No.of Pages: 2

: SEMB ZC415 : Data Structures and Algorithms : Comprehensive examination (Open book) Weightage : 60% : 3 Hours : 17/5/2009 Time: 10.00 AM to 01.00 PM No. of Questions: 6

_______________________________________________________________________. Q.1 a) Write an algorithm to reverse the singly linked list. (8) All the steps of algorithm needs to be explained with diagrammatic demonstration. Algorithm should reverse the singly linked list completely that is the last node should become the first and so on. b) List the applications of Linked List (2) Polynomial Addition and Multiplication Multiplication of large integers Sparse matrix Graph representation Operating System : PCB are arranged in linked list Etc At least 4 applications are expected Q. 2 a. Explain Prim’s algorithm and apply the same on the following graph to find the Minimum Spanning Tree. (6) 10 A

D 15

10

C

4

30

B

2 E

2 20

F 15

10 Show all the steps. Step by step explanation should be given along with the diagrams. If without showing the steps, direct spanning tree is drawn then only one mark should be allotted.

b. Show the representation of the above graph using: i) Adjacency Matrix ii) Adjacency List Representation of the above graph as Adjacency matrix Representation of the above graph as Adjacency List

(4) (2) (2)

Q.3 Discuss the applications of BST and construct the BST with the following data: STA, ADD, LDA, MOV, JMP, TRIM, XCHG, MUI, DIV, NOP, IN, JNZ Show all the steps. (10) If the data is huge and searching is the more frequent operation then BST is the suitable data structures. Application can be to store the dictionary of the words.. (2) All the steps while constructing the BST should be shown with diagrams. (8) If directly the BST is drawn then only one mark should be allotted for that. Q.4 Explain all the steps of Dijkstra’s algorithm. Apply the same to find out the shortest path from F to A and also find the length of the shortest path. (10) 10 A

D 15

10

C

4

30

B

2 E

2 20

F 15

10 Step by step details along with the calculation details should be shown with explanation. Finding the length(cost) of the shortest path: 8 marks Finding the path : 2 marks Q.5 a. Write note on “Dynamic Programming” Answer should contain the why dynamic programming is required, what is dynamic programming and how to implement the same

(5)

b. Discuss the term “Efficiency of the algorithm” and explain the parameters on which it depends. (5) Answer should start with the factors affecting the efficiency ( time and space ) and then various types of times and memories till it reaches to “size of data”.

Q.6 a. Explain the quick sort algorithm and trace the same on the following data. Show each step with explanation: 21, 32, 65, 2, 32, 1, 98, 53, 42, 12 (6) Explanation of Quick sort algorithm: 2 marks Showing each step while tracing the given list: 4 marks b. Discuss the need of using AVL tree as a data structure (4) Answer should contain the drawbacks of unbalanced tree and then the advantages of using AVL

All the Best