Jaypee Institute of Information Technology (JIIT) 2008 B.E Test 3 : Fundamentals of Algorithm - Question Paper
jaypee university of information teciinogi.ogy
WAKNAGIIAT, Minor- III, November 2008 K. Tech. BI, V Scm
Course Name: Fundamentals of Algorithm Max. Marks: 30 Course Code: 07B41C1106 Max. Time: 90 min. Course Credit: 4____
Question 1. Implement an ordercd-statistic tree using a B-trec. Divide your answer in following sections:
a Describe the changcs required in the basic Data - Structure of a B-trcc to implement an Ordered - Statistic tree, b. Write an algorithm to find an dement at a particular rank in the B-uee in 0(log n) time, n is the number of element in the B-tree.
(Marks: 61
Question 2. What is the largest possible number of internal nodes in a Red-Black tree with a black height k? What is the smallest possible number?
(Marks: 3]
Question 3. Among R.ed-Black tree and AVL-tree which is a better self balancing tree? Why? Explain with example.
|Marks: 3|
Question 4. Find the optimum sequence of multiplication for the following dimensions of a matrix chain :
{5,10,20, 6.5,10.3}
(Marks: 5]
Question 5. Given an atray sorted in the reverse order of that which is required, which among the following is the best sort for such an array and why?
a. Bubble Son
b. Insertion Sort
c. Merge Sort
d. Heap Sort
Give reason for each why they arc they arc not the best sort for such an array.
(Marks: 4] .
**>
Question 6. Suppose all the edge weights in a graph are integers in the range from 1 to V. How fast can you make Kruskal's algorithm run? What if the edge weights arc integers in the range from I to W for some W?
|Marks: 3|
|
Attachment: |
| Earning: Approval pending. |
