Jaypee Institute of Information Technology (JIIT) 2008 B.E Computer Science Test 1 : Fundamentals of Algorithm For CSE - Question Paper

JAYPEE UNIVERSITY INFORMATION TECHNOLOGY Test -1 Batch : CSE & IT 4^,h Semester

Course Name: Fundamentals of Algorithm    Course Code: 07B41CM06

Credits: 4    Time: 1 Hr.

Maximum Marks: 20

Note : All Questions are compulsory_

M REFERENCE ONLY

Question 1. Prove formally that every AVL tree is a Red-Black tree, i.e., tnarevery AVL tree can have its nodes colored in red or black such that:

a.    Root and Leaves (NULL) are black.

b.    Every red node has a black parent

c.    The number of black nodes is the same on each path from the root to a leaf.

[Marks: 4|

Question 2. Write an algorithm which takes an AVL tree as an input and converts it to a Red-Black tree by giving every node a color (either red of black).

Assume that every node of the AVL tree has a field for the color already.

[Marks: S)

Question 3. Solve the Dutch National Flag problem. You are given an array filled with elements that can take one of only 3 values red, white and blue. The goal is to return an array where all the red elements are to the left, all the blue elements are to the right and white elements are in the middle.

Your algorithm should take linear (ime. You can only exchange the elements, only one extra variable for the exchange can be used. No other variables other than the loop indices can be used. Specifically no counters are to be used to count the number of red, blue or white elements.

[Marks: 5|

Question 4. Do the following operation on an AVL tree:

a.    Insert Values : 34, 78, 56, 17,39,36,13,35

[Marks: 4|

b.    Delete Values: 56,13

(Marks: 2]

Attachment: jaypee-institute-of-information-technology--jiit--2008-b-e-computer-science-21294-1.jpg

Earning:   Approval pending.