Jaypee Institute of Information Technology (JIIT) 2008 M.Tech Computer Science test 3 - Question Paper
i c3 I Rnd
JAYPKE IMVhRSn V Oi INFORMATION ILCHMX.I.OCY WAKNAGI!AT. Minor- III, No>ember 21108 M. Tech. CSE, I Sent (bourse Name: Advanced Data Structure* \Ui. Murk*: 30 Course Credit: 3, C.&P6 : Q7MHCMQI_Max. Time: 90 min.
Question I. Show that for all n G N\ there exists an AVI tree for which the deletion ot' a node would cause n rotations (single or double). Show how such a tree is constructed, show the node to he deleted and explain why n rotations are necessan and sufficient.
i c3 I Rnd
(Marks: 4]
i c3 I Rnd
Question 2. In NOIDA toll way the toll collections uses a computerised toll collection system. The highway is modeled as an ordered list or toll booths
i c3 I Rnd
/;. t)...../ in which toll t, collects the toll of Rs.<7, 0< i < n. Design a
Data Structure that can perform the following operation in 0(log ) time
i. Insert a new toil booth h after with toll Rs.w
ii. Delete toll f*
iii. Add Rs.0 to the toll of all the toll booths from i, till f, both included.
i c3 I Rnd
(Mark*: 81
Question Given an array </[l...n] of integers, consider the problem of
finding the longest monoionicolly increasing subsequence of noi necessarily contiguous entries in your array For example, if the entries arc 10, 3, 9, 5, 8, 13. II, 14. then a longest monotonicaily increasing subsequence is 3. 5. 8. 11. 14 The goal of this problem is to find an efficient dynamic programming algorithm for solving this problem.
i c3 I Rnd
(Markc 8]
Question 4. Using depth first search, outline an algorithm that determines whetlter the edges of a connected, undirected graph can be directed to produce a strongly connected directed graph. If so, the algorithm outputs such an orientation of the edges.
i c3 I Rnd
(Marks: 5]
Question 5. Suppose that li-TRliH-SEARCH is implemented to use binary search rather than linear search within each node. Show.jhai this change makes the CPU time required 0(lg ). independently of how / might be chosen as 3 function of n.
i c3 I Rnd
I'larks: 2]
Question 6. Show the results of inserting the keys
F.S. Q, K. C. i. H, T. V, W, M, R. N.P.A. 8.X. Y. D. Z. E in order into an empty B-tree with minimum degree 2. Only draw the configurations of the tree just before some node must split, and also draw the final configuration.
i c3 I Rnd
(Marks: 3|
|
Attachment: |
| Earning: Approval pending. |
