Q1. Show that the Red-Black tree which results after the successive insertions of the keys 51, 48, 45, 23, 30 to an initially empty tree. Delete 51 from the resulting tree.
Q2. Write down a topological sort for the given relation:
(a < b, a < c, d < b, e < c, a < e, a < d)
Q3. Illustrate the execution of the dynamic programming algorithm for the longest common subsequences on the given illustration:
X =
Y =
What are the final LCS and its length?
Q4. Describe the Quick sort and find out its running time (average case, best case and worst case).
Q5. Describe the operation of BUCKET SORT on the array:
A = <0.79, 0.29, 0.1, 0.35, 0.49, 0.45, 0.13, 0.38>
Q6. Write down the linear time in-place algorithm to rearrange an array of n keys so that all the even-valued keys precede all the odd-valued keys. Illustrate that your algorithm runs in the linear time.