Data Structures and Problem Solving - Jun 2015

Computer Engineering (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.

Answer any one question from Q1 and Q2

1 (a) Write a pseudo 'C' code to implement quick sort. Derive time complexity of quick sort in best and worst case.(6 marks) 1 (b) Derive the code for the following message using Huffman encoding 'A B R A K A D A B R A'.(6 marks) 2 (a) Sort the following data using merge sort: [10, 5, 15, 3, 20, 1, 30, 9].(3 marks) 2 (b) Write recursive function to calculate a^b.(3 marks) 2 (c) Create a binary tree from the following inorder and postorder traversals. Also write preorder traversal of the constructed tree:

Answer any one question from Q3 and Q4

3 (a) Write algorithm for Breadth First Traversal of the graph. Also write its complexity.(6 marks) 3 (b) Construct the AVL tree for the following data: 20, 1, 2, 25, 15, 70, 30, 75, 10, 35. Show clearly rotation used.(6 marks) 4 (a) Find the shortest path from a to f, in the following graph using Dijkstra's Algorithm. (6 marks) 4 (b) Write 'C' code for the following function w.r.t. AVL tree:
(i) Rotate Left
(ii) Rotate Right(6 marks) 4 (c) For the hash table size of 10 using hash function key F(key) = key % 10 insert the following keys: 65, 75, 25, 29, 85, 39, 36. Use linear probing with chaining.(3 marks)

Answer any one question from Q5 and Q6

5 (a) Sort the following data in descending order using heap sort 85, 15, 25, 95, 145, 55, 165, 75. Show all steps.(5 marks) 5 (b) Construct B+ tree of order 3 for the following data: 10, 2, 30, 5, 90, 100, 50, 75, 35, 25.(4 marks) 5 (c) Write 'C' program to read 10 integers from keyboard and store them in the file 'My File'.(4 marks) 6 (a) Create Min Heap for the following data using repeated insertion method 5, 7, 2, 3, 9, 1, 10.(4 marks) 6 (b) What is B tree ? Explain the procedure to delete node from B tree.(3 marks) 6 (c) Explain random access file and sequential file.(3 marks) 6 (d) Explain the following operation on sequential file:
i) Creation
ii) Read
iii) Insert.(3 marks)

Answer any one question from Q7 and Q8

7 (a) Find the largest number among the following using parallel Computation: 10, 3, 2, 8, 30(6 marks) 7 (b) Write a parallel algorithm for odd even merge sort.(4 marks) 7 (c) Explain in detail parallel computation model.(3 marks) 8 (a) Explain the list ranking problem. Explain with example how will you solve it using pointer jumping techniques.(6 marks) 8 (b) Compute prefix sum (8, 2, -1, 5) using binary tree techniques.(4 marks) 8 (c) Write notes on:
i) CRCW
ii) EREW
iii) CREW(3 marks)